package algorithm.tree.theadedBinaryTree;

/**
 * 中序线索二叉树
 */
public class ThreadedTree {
    //当前节点的前一个节点
    static TreeNode pre = null;

    public static void main(String[] args) {
        TreeNode head = new TreeNode(1, "宋江");
        TreeNode node2 = new TreeNode(2, "吴用");
        TreeNode node3 = new TreeNode(3, "卢俊");
        TreeNode node4 = new TreeNode(4, "林冲");
        head.left = node2;
        head.right = node3;
        node3.right = node4;
        BinaryTree bt = new BinaryTree(head);
        begin(bt);
        //测试代码
//        System.out.println(head);
        System.out.println(node2.right);
//        System.out.println(node3);
//        System.out.println(node4);

    }

    public static void begin(BinaryTree bt) {
        if (bt.head == null)
            return;
        Threaded(bt.head);
    }

    //按照中序遍历的顺序线索化
    public static void Threaded(TreeNode node) {
        //线索化左子树
        if (node.left != null)
            Threaded(node.left);

        //线索化当前节点
        //线索化left指针
        if (node.left == null) {
            node.left = pre;
            node.leftType = 1;
        }
        //线索化right指针
        if (pre != null && pre.right == null) {
            pre.right = node;
            pre.rightType = 1;
        }
        //将pre指针后移
        pre = node;
        //线索化右子树

        if (node.right != null)
            Threaded(node.right);
    }
}
